/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._118;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._118
 * @ClassName: PascalsTriangle
 * @Author: linyaonan
 * @Date: 2019/11/5 14:16
 */
public class PascalsTriangle {

    public List<List<Integer>> generate(int numRows) {
        // 外层集合
        List<List<Integer>> pList = new ArrayList<>();
        if (numRows <= 0) {
            return pList;
        }

        if (numRows == 1) {
            addOne(pList);
            return pList;
        }
        if (numRows == 2) {
            addTwo(pList);
            return pList;
        }
        addTwo(pList);
        int count = 3;
        while (count <= numRows) {
            List<Integer> thisList =  pList.get(count - 2);
            List<Integer> nextListFromThis = getNextListFromThis(thisList);
            pList.add(nextListFromThis);
            count++;
        }
        return pList;
    }

    private void addOne(List<List<Integer>> pList) {
        List<Integer> iList = new ArrayList<>();
        iList.add(1);
        pList.add(iList);
    }

    private void addTwo(List<List<Integer>> pList) {
        addOne(pList);
        List<Integer> iList2 = new ArrayList<>();
        iList2.add(1);
        iList2.add(1);
        pList.add(iList2);
    }

    /**
     * 从当前数组生成下一个的数组
     * @param list
     * @return
     */
    private List<Integer> getNextListFromThis(List<Integer> list) {
        List<Integer> iList = new ArrayList<>();
        if (list!= null && list.size() != 0) {
            // 头数据
            iList.add(1);
            for (int i = 0; i < list.size() - 1; i+=1) {
                Integer lNum = list.get(i);
                Integer rNum = list.get(i + 1);
                iList.add(lNum+rNum);
            }
            iList.add(1);
        }
        return iList;
    }

    /**
     * 动态规划
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> r = new ArrayList<>();
        List<Integer> preList = new ArrayList<>();
        for (int i = 1; i <= numRows; i++) {
            List<Integer> build = build(i, preList);
            r.add(build);
            preList = build;
        }
        return r;
    }

    /**
     * 根据层号以及上一层的数据生成当前的层结果，
     * @param row
     * @param preList
     * @return
     */
    private List<Integer> build(int row, List<Integer> preList) {
        if (preList.isEmpty() || row == 1) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(1);
            return list;
        }
        if (row == 2) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(1);
            list.add(1);
            return list;
        }
        ArrayList<Integer> result = new ArrayList<>();
        // 收尾必然是1
        result.add(1);

        for (int i = 0; i < preList.size() - 1; i++) {
            int add = preList.get(i) + preList.get(i + 1);
            result.add(add);
        }
        result.add(1);
        return result;
    }

}
